﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    public class Solution13
    {
        public int Search(int[] nums, int target)
        {
            if (nums.Length==0)
            {
                return -1;
            }
            if (nums.Length==1)
            {
                if (nums[0] == target)
                {
                    return 0;
                }
                else
                {
                    return -1;
                }
            }
            int left = 0;
            int right =nums.Length-1;
            
            while (left <= right)
            {
                int mid = (left + right) / 2;
                if (nums[mid] == target)
                {
                    return mid;
                }
                else if (nums[mid] < nums[right])
                {
                    if (nums[mid] < target && target<=nums[right])
                    {
                        left = mid + 1;
                    }
                    else
                    {
                        right = mid - 1;
                    }
                }
                else 
                {
                    if (nums[left] <=target && target<nums[mid])
                    {
                        right = mid - 1;
                    }
                    else
                    {
                        left = mid + 1;
                    }
                }              
            }
            return -1;
        }
    }
}
